package number;

public class NextPalindrome {
  
  static void generateNextPalindromeUtil (int num[], int n )
  {
      // find the index of mid digit
      int mid = n/2;
   
      // A boolean variable to check if copy of left side to right is sufficient or not
      boolean leftsmaller = false;
   
      // end of left side is always 'mid -1'
      int i = mid - 1;
   
      // Begining of right side depends if n is odd or even
      int j = (n % 2 == 0)? mid + 1 : mid;
   
     // Initially, ignore the middle same digits 
      while (i >= 0 && num[i] == num[j]){
          i--;j++;
      }
   
      // Find if the middle digit(s) need to be incremented or not (or copying left 
      // side is not sufficient)
      if ( i < 0 || num[i] < num[j])
          leftsmaller = true;
   
      // Copy the mirror of left to tight
      while (i >= 0)
      {
          num[j] = num[i];
          j++;
          i--;
      }
   
      // Handle the case where middle digit(s) must be incremented. 
      // This part of code is for CASE 1 and CASE 2.2
      if (leftsmaller == true)
      {
          int carry = 1;
          i = mid - 1;
   
          // If there are odd digits, then increment
          // the middle digit and store the carry
          if (n%2 == 1)
          {
              num[mid] += carry;
              carry = num[mid] / 10;
              num[mid] %= 10;
              j = mid + 1;
          }
          else
              j = mid;
   
          // Add 1 to the rightmost digit of the left side, propagate the carry 
          // towards MSB digit and simultaneously copying mirror of the left side 
          // to the right side.
          while (i >= 0)
          {
              num[i] += carry;
              carry = num[i] / 10;
              num[i] %= 10;
              num[j++] = num[i--]; // copy mirror to right
          }
      }
  }
   
  // The function that prints next palindrome of a given number num[]
  // with n digits.
  static void generateNextPalindrome( int num[], int n )
  {
      int i;
   
      
   
      // Input type 1: All the digits are 9, simply o/p 1
      // followed by n-1 0's followed by 1.
      if( AreAll9s(num, n ) == 1)
      {
          System.out.print( "1 ");
          for( i = 1; i < n; i++ )
            System.out.print( "0 " );
          System.out.print( "1" );
      }
   
      // Input type 2 and 3
      else
      {
          generateNextPalindromeUtil ( num, n );
   
          // print the result
          printArray (num, n);
      }
  }
   
  // A utility function to check if num has all 9s
  static int AreAll9s( int[] num, int n )
  {
      int i;
      for( i = 0; i < n; ++i )
          if( num[i] != 9 )
              return 0;
      return 1;
  }
   
  /* Utility that prints out an array on a line */
  static void printArray(int arr[], int n)
  {
      int i;
      for (i=0; i < n; i++)
        System.out.print(arr[i]);
      System.out.print("\n");
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int num[] = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2};
    
    int n = 11;
 
    generateNextPalindrome( num, n );
  }

}
